package com.java.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定⼀个数组和⼀个⽬标和，从数组中找两个数字相加等于⽬标和，输出这两个数字的下标。讲⼀个元素只能⽤⼀次。
 */
public class code_01 {


    public static void main(String[] args) {


        int[] num = {2,4,7,8,9,11,14};

//        int sum = num[0] + num[2];
//        System.out.println(sum);
//        for (int i = 0; i < num.length; i++) {
//            System.out.println(i);
//        }

        int target= 9;
        int[] extracted = oneSum(num, target);
        for (int i = 0; i < extracted.length; i++) {
            System.out.print(extracted[i] + " ");
        }

        System.out.println("===================================");

        int[] ints = towSum(num, target);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+ " ");
        }

        System.out.println("=====================================");

        int[] ints1 = threeSum(num, target);
        for (int i = 0; i < ints1.length; i++) {
            System.out.print(ints[i]+ " ");
        }

    }

    /**
     * 方式二:
     * 有没有⼀种⽅法，不⽤遍历就可以找到元素⾥有没有等于 sub 的？
     * hash table ！！！
     * 我们可以把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value 。
     */
    private static int[] towSum(int[] num, int target){

        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < num.length; i++) {
            map.put(num[i], i);//key：具体的数  value：数组下标
        }
        for (int i = 0; i < num.length; i++) {
            int sub = target - num[i];
            //map.get(sub)!=i ： 自己不能和自己相加,⼀个元素只能⽤⼀次。
            if (map.containsKey(sub) && map.get(sub)!=i){
                return new int[]{i , map.get(sub)};//索引对应的值
            }
        }
//        throw new IllegalArgumentException("No two sum solution");
        return null;
    }

    /**
     * 优化方式二
     */
    private static int[] threeSum(int[] num, int target){

        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < num.length; i++) {
            int sub = target - num[i];
            //map.get(sub)!=i ： 自己不能和自己相加⼀个元素只能⽤⼀次。
            if (map.containsKey(sub)){
                return new int[]{i , map.get(sub)};
            }
            map.put(num[i], i);//key：具体的数  value：数组下标
        }
        throw new IllegalArgumentException("No two sum solution");

    }




    /**
     * 方式一
     */
    private static int[] oneSum(int[] num, int target) {
        int[] arr = new int[2];
        for (int i = 0; i < num.length; i++) {
            for (int j = 1; j < num.length; j++) {
                if (num[i]+ num[j] == target){
//                    System.out.println(i +" " + j);
                    arr[0]=i;
                    arr[1]=j;
                }
            }

        }
        return arr;
    }



}
